/*
    This program is free software: you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation, either version 3 of the License, or
    (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with this program.  If not, see <http://www.gnu.org/licenses/>.
*/

/* generate geometry on all voxels, therefore thickening the object
 */

#pragma once

#include "NTree.h"
#include "AuxMath.h"
#include "Constructors.h"
#include "Geometry/RoundedCube.h"
#include "Geometry/Helpers.h"

//this class takes a shape as an input and tests it against a tree
template<class VecType, class DataType, class Shape>
class ShapeTest
{
private:
	typedef typename NTree<VecType, DataType>::Node treeNode;

	class SStack
	{
	public:
		const treeNode* pNode;
		Area<VecType> area;

		SStack() : pNode(nullptr), area(Area<VecType>())
		{}

		SStack(const treeNode& node, const Area<VecType>& area) : pNode(&node), area(area)
		{}

	};
	static void
	seedStack(const Shape& shape, const NTree<VecType, DataType>& t,
			SStack* pStack, int* pnStackSize)
	{
		Area<VecType> subAreas[VecType::childCount];
		t.subAreas(subAreas);

		//OLD CODE
		for(unsigned int iNode=0; iNode<VecType::childCount; iNode++)
		{
			pStack[iNode].pNode=&t.constGetRoot(iNode);
			pStack[iNode].area=subAreas[iNode];
		}
		*pnStackSize=VecType::childCount;

/*
		//save some cycles by checking only areas inside the bounds of the shape
		Area<VecType> boundAreas[VecType::childCount];
		GeomHelpers<VecType>::getAreas(boundAreas, shape.getBounds());

		Area<VecType> scanAreas[VecType::childCount*2];
		unsigned int nAreas;
		GeomHelpers<VecType>::intersectAreas(scanAreas, nAreas, subAreas, boundAreas);
		*pnStackSize=nAreas;

		for(unsigned int iNode=0; iNode<nAreas; iNode++)
		{
			VecType vTarget=scanAreas[iNode].toBox().min;
			VecType pivot(0);
			Exponent expo = t.getSize()+1,
					targetExpo=scanAreas[iNode].expo;

			const treeNode* pNodes=&t.constGetRoot(0);
			const treeNode* pNode;

			do
			{
				unsigned int iQuadrant = BoxTests<VecType>::getQuadrant(pivot, vTarget);

				//sadly can't assign a new memory address to our pointer
				const treeNode* pTemp=&(pNodes[iQuadrant]);
				memcpy(&pNode, &pTemp, sizeof(treeNode*));


				const treeNode* pNext=&(pNodes[iQuadrant].constGetSubNode(0));
				memcpy(&pNodes, &pNext, sizeof(treeNode*));

				expo--;
				unsigned int uiHalfExtent=AuxMath::pow2(expo-1);
				pivot = pivot + BoxTests<VecType>::getBoxVertex(
								Box<VecType>(VecType(-(int)uiHalfExtent), VecType(uiHalfExtent) ),
								iQuadrant);

				//check if we reached a dead end
				if(pTemp->getType()!=Both)
					break;
			}while(expo != targetExpo);

			pStack[iNode].pNode=pNode;
			pStack[iNode].area=scanAreas[iNode];

			if(expo != targetExpo)
				//adjust area
				pStack[iNode].area=Area<VecType>(expo, GeomHelpers<VecType>::shiftDown(pivot, expo));
		}
*/
	}

public:
	static bool isEmpty(const Shape& shape, const NTree<VecType, DataType>& t)
	{
		return (!isNonEmpty(shape, t));
	}

	static bool isNonEmpty(const Shape& shape, const NTree<VecType, DataType>& t)
	{
		SStack* pStack=new SStack[(1+t.getSize()) * VecType::childCount];
		int iStackPos;

		seedStack(shape, t, pStack, &iStackPos);

		Area<VecType> subAreas[VecType::childCount];

		VoxelType type;
		RangeRelation rel;

		while(--iStackPos>=0)
		{
			const treeNode& node = *(pStack[iStackPos].pNode);
			type=node.getType();
			if(type==Nil)
				continue;//early out

			const Area<VecType>& area = pStack[iStackPos].area;
			rel=shape.testBox(area.toBox());

			switch(rel)
			{
			case Outside:
				break;
			case Inside:
				//if Both or Solid -> true
				delete pStack;
				return true;
			default:
				switch(type)
				{
				case Both:
					area.subAreas(subAreas);
					//overwrite current stack element
					for(unsigned int iNode=0; iNode<VecType::childCount; iNode++)
					{
						pStack[iStackPos+iNode].pNode=&node.constGetSubNode(iNode);
						pStack[iStackPos+iNode].area=subAreas[iNode];
					}
					iStackPos+=VecType::childCount;
					break;
				case Solid:
					delete pStack;
					return true;
				default:
					break;
				}
				break;
			}
		}
		delete pStack;
		return false;
	}

	static bool isSolid(const Shape& shape, const NTree<VecType, DataType>& t)
	{
		return (!isNonSolid(shape, t));
	}

	static bool isNonSolid(const Shape& shape, const NTree<VecType, DataType>& t)
	{
		if(shape.testBox(t.getBox())==Outside)
			return true;
		Area<VecType> subs[VecType::childCount];
		t.subAreas(subs);

		for(unsigned int i=0; i<VecType::childCount; i++)
			if(nonSolidRecursion(shape, t.constGetRoot(i), subs[i]))
				return true;
		//filter cases where the query is outside tree bounds

		return false;
	}
private:
	static bool nonSolidRecursion(const Shape& shape,
			const typename NTree<VecType, DataType>::Node& node,
			const Area<VecType> &area)
	{
		const VoxelType type=node.getType();
		if(type==Solid)
			return false;//early out

		Area<VecType> subAreas[VecType::childCount];
		RangeRelation rel=shape.testBox(area.toBox());
		switch(rel)
		{
		case Outside:
			return false;
		case Inside:
			//if Both or Nil -> true
			return (type!=Solid);
		default:
			switch(type)
			{
			case Both:
				area.subAreas(subAreas);
				for (unsigned int i = 0; i < VecType::childCount; i++)
					if(nonSolidRecursion(shape, node.constGetSubNode(i), subAreas[i]))
						return true;
				return false;
			case Solid:
				return false;
			default:
				return true;
			}
			break;
		}
		printf("shouldn't happen!\n");
	}
};
/*
template<class VecType, class DataType>
class BoxThickenCon
{
public:
	BoxThickenCon(const VecType& extents, const NTree<VecType, DataType>& t) :
		tree(t), thickExt(extents*2), copyCon(t),
		size(AuxMath::log2((extents*2).maxComponent() + AuxMath::pow2(t.getSize()) ) )
	{
	}
	const int getSize() const {return size;}

	const VoxelType fn(const Box<VecType>& box) const
	{
		VecType center=(box.min + box.max).half();
		VecType queryExt=box.max - box.min;
		VecType solidExt=thickExt-queryExt;
		VecType bothExt=thickExt+queryExt;

		Box<VecType> solidBox=boxFromExt(center, solidExt),
				bothBox=boxFromExt(center, bothExt);

		//check whether there is a negative component in solidExt
		bool bNeg=false;
		if(solidExt.x<0)
		{
			solidExt.x=-solidExt.x;
			bNeg=true;
		}
		if(solidExt.y<0)
		{
			solidExt.y=-solidExt.y;
			bNeg=true;
		}
		if(solidExt.z<0)
		{
			solidExt.z=-solidExt.z;
			bNeg=true;
		}

		VoxelType type=copyCon.fn(solidBox);
		if(type==Solid)
			return Solid;
		if(type==Both && !bNeg)
			return Solid;

		type=copyCon.fn(bothBox);
		if(type==Nil)
			return Nil;
		return Both;
	}
private:
	const NTree<VecType, DataType>& tree;
	VecType thickExt;
	const CopyCon<VecType, DataType> copyCon;
	int size;
};
*/
///Copies an existing tree.
template<class VecType, class DataType>
class SphereThickenCon
{
public:
	SphereThickenCon(const NTree<VecType, DataType>& t, const float& r, const bool bGrowTree=true) :
		tree(t), r(r), bGrowTree(bGrowTree),
		size(bGrowTree ?
				(1 + AuxMath::log2((int)(2.0f*r + AuxMath::pow2(tree.getSize()) ) )) :
				(tree.getSize())
				)
	{}
	const int getSize() const {return size;}

	const VoxelType fn(const Box<VecType>& box) const
	{
		//level 0 gate
		if(box.min==box.max)
		{
			Sphere<VecType> sph(r, box.min);
			//if there is anything inside the check sphere -> solid
			if(ShapeTest<VecType, DataType, Sphere<VecType>>::isNonEmpty(sph, tree))
			{
				return Solid;
			}

			//nothing inside -> nil
			//no both case, since level 0
			return Nil;
		}

		VecType center, queryExt;
		BoxTests<VecType>::box2Ext(box, center, queryExt);

		VecType solidExt=VecType((typename VecType::scalarType)(2.0f*r))-queryExt;

		//check whether there is a negative component in solidExt
		bool bNeg=false;
		for (unsigned int iDim = 0; iDim < VecType::dimension; iDim++)
			if(solidExt[iDim]<0)
			{
				bNeg=true;
				break;
			}

		if(bNeg)
		{
			VecType solidBoxExt=queryExt-VecType((typename VecType::scalarType)(1.414f*r));
			Box<VecType> box;
			BoxTests<VecType>::ext2Box(center, solidBoxExt, box);

			if(ShapeTest<VecType, DataType, Box<VecType> >::isSolid(box, tree))
				return Solid;
		}
		else
		{//bNeg is false -> only Both required
			RoundedCube<VecType> rcSolid(center, solidExt, r);
			if(ShapeTest<VecType, DataType, RoundedCube<VecType> >
				::isNonEmpty(rcSolid, tree))
				return Solid;
		}
		VecType bothExt=VecType((typename VecType::scalarType)(2.0f*r))+queryExt;
		RoundedCube<VecType> rcBoth(center, bothExt, r);

		if(ShapeTest<VecType, DataType, RoundedCube<VecType>>
			::isEmpty(rcBoth, tree))
			return Nil;

		return Both;
	}

private:
	const NTree<VecType, DataType>& tree;
	const float r;
	const bool bGrowTree;
	const int size;
};

//extrudes a  2D shape into two dimensions
//2D shape positioned in x,y-plane
template<class VecType, class DataType>
class StraightExtrusion
{
public:
	StraightExtrusion(const NTree<typename VecType::lowerDim, DataType>& base, VecType vDir, float fTwistRate, float fTaper) :
		base(base),
		vDir(vDir),
		fTwistRate(fTwistRate),
		fTaper(fTaper),
		zMin(std::min(vDir.getComponent(VecType::dimension-1), 0)),
		zMax(std::max(vDir.getComponent(VecType::dimension-1), 0)),
		bPositiveDir(zMax>0),
		size(1+AuxMath::log2( AuxMath::pow2(base.getSize()) + vDir.maxComponent()))
	{

	}
	const unsigned int getSize() const {return size;}

	const VoxelType fn(const Box<VecType>& box) const
	{
		//clip stuff outside z-range
		switch(checkRangesSorted<typename VecType::scalarType>(
				box.min.getComponent(VecType::dimension-1),
				box.max.getComponent(VecType::dimension-1),
				zMin, zMax))
		{
		case Outside:
			return Nil;
		case Inside:
			break;
		default:
			return Both;
		}

		Box<typename VecType::lowerDim> projBox;

		for(unsigned int uiDim=0; uiDim<VecType::lowerDim::dimension; uiDim++)
		{
			projBox.min[uiDim]=box.min.getComponent(uiDim);
			projBox.max[uiDim]=box.max.getComponent(uiDim);
		}

		//printf("%s, %s -> ", projBox.min.toString().c_str(), projBox.max.toString().c_str());

		if(ShapeTest<typename VecType::lowerDim, DataType, Box<typename VecType::lowerDim> >::isEmpty(projBox, base))
		{
			//printf("Nil\n");
			return Nil;
		}
		if(ShapeTest<typename VecType::lowerDim, DataType, Box<typename VecType::lowerDim> >::isSolid(projBox, base))
		{
			//printf("Solid\n");
			return Solid;
		}

		//printf("Both\n");
		return Both;
	}
private:
	const NTree<typename VecType::lowerDim, DataType>& base;
	const VecType vDir;
	const float fTwistRate;
	const float fTaper;
	const typename VecType::scalarType zMin, zMax;
	const bool bPositiveDir;
	const unsigned int size;
};
